<?php
/**
 * 并查集
 * User: liuqingwei
 * Date: 2020/4/4
 * Time: 上午11:14
 */

class QuickFind
{
    public $data;
    public $count;
    
    /**
     * 初始化生成数据
     *
     * @param int $count 数量
     *
     * @return mixed
     */
    public function __construct(int $count)
    {
        $this->count = $count;
        for($i=0;$i<$count;$i++)
        {
            $this->data[$i] = $i;
        }
    }
    
    /**
     * 查找
     *
     * @param int $q 元素
     *
     * @return mixed
     */
    public function find(int $q)
    {
        return $this->data[$q];
    }
    
    /**
     * 是否连接
     *
     * @param int $q 索引
     * @param int $p 索引
     *
     * @return boolean
     */
    public function isConnect(int $q,int $p)
    {
        return $this->find($q) == $this->find($p);
    }
    
    /**
     * 合并
     *
     * @param int $q 索引
     * @param int $p 索引
     *
     * @return mixed
     */
    public function mergeElement(int $q,int $p)
    {
        $q_id = $this->find($q);
        $p_id = $this->find($p);
        
        if ($q_id == $p_id)
        {
            return;
        }
        
        for($i=0;$i<$this->count;$i++)
        {
            if ($this->data[$i] == $q_id)
            {
                $this->data[$i] = $p_id;
            }
        }
    }
}

$n = 20000;
$obj = new QuickFind($n);
$before_time = microtime(true);
for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->mergeElement($a,$b);
}

for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->isConnect($a,$b);
}
$after_time = microtime(true);
$time = round($after_time-$before_time,3);
echo 'QuickFind耗时'.$time.'秒'.PHP_EOL;

/**
 * 并查集优化
 *
 * 把每个节点都看作一个整体
 *
 * 若实现节点之间的连接，只需要，使其根节点连接即可
 *
 */
class QuickFindOptimization
{
    public $parent;
    public $count;
    
    public function __construct(int $count)
    {
        $this->count = $count;
        for($i=0;$i<$this->count;$i++)
        {
            $this->parent[$i] = $i;
        }
    }
    
    /**
     * 查找根节点
     *
     * @param int $q 查找的元素
     *
     * @return int
     */
    public function find(int $q)
    {
        while($q != $this->parent[$q])
        {
            $q = $this->parent[$q];
        }
        
        return $q;
    }
    
    
    /**
     * 判断两个元素是否连接
     *
     * @param int $q 查找的元素
     * @param int $p 查找的元素
     *
     * @return bool
     */
    public function isConnect(int $q,int $p)
    {
        return $this->find($q) == $this->find($p);
    }
    
    /**
     * 合并元素连接
     *
     * @param int $q 合并的元素
     * @param int $p 合并的元素
     *
     * @return bool
     */
    public function mergeElement(int $q,int $p)
    {
        //找到两个元素的根节点
        $q_root = $this->find($q);
        $p_root = $this->find($p);
        
        if ($q_root == $p_root)
        {
            return;
        }
        
        //绑定
        $this->parent[$q_root] = $p_root;
    }
}

$obj = new QuickFindOptimization($n);
$before_time = microtime(true);
for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->mergeElement($a,$b);
}

for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->isConnect($a,$b);
}
$after_time = microtime(true);
$time = round($after_time-$before_time,3);
echo 'QuickFindOptimization耗时'.$time.'秒'.PHP_EOL;
/**
 * 并查集优化
 *
 * 把每个节点都看作一个整体
 *
 * 若实现节点之间的连接，只需要，使其根节点连接即可
 *
 */
class QuickFindOptimizationTWo
{
    public $parent;
    public $count;
    public $sz;//sz统计集合大小
    //public $rank;//引入以rank作为树高
    
    public function __construct(int $count)
    {
        $this->count = $count;
        for($i=0;$i<$this->count;$i++)
        {
            $this->parent[$i] = $i;
            $this->sz[$i] = 1;
            $this->rank[$i] = 1;
        }
    }
    
    /**
     * 查找根节点
     *
     * @param int $q 查找的元素
     *
     * @return int
     */
    public function find(int $q)
    {
        while($q != $this->parent[$q])
        {
            //启用路径压缩，隔一个路径去找父节点
            $this->parent[$q] = $this->parent[$this->parent[$q]];
            $q = $this->parent[$q];
            
            //递归实现的递归压缩，实践效果并不是很好，虽然树高降低了，但是由于递归，导致总的时长变慢了
//            $this->parent[$q] = $this->find($this->parent[$q]);
//            $q = $this->parent[$q];
            
        }
        
        return $q;
    }
    
    
    /**
     * 判断两个元素是否连接
     *
     * @param int $q 查找的元素
     * @param int $p 查找的元素
     *
     * @return bool
     */
    public function isConnect(int $q,int $p)
    {
        return $this->find($q) == $this->find($p);
    }
    
    /**
     * 合并元素连接
     *
     * @param int $q 合并的元素
     * @param int $p 合并的元素
     *
     * @return bool
     */
    public function mergeElement(int $q,int $p)
    {
        //找到两个元素的根节点
        $q_root = $this->find($q);
        $p_root = $this->find($p);
        
        if ($q_root == $p_root)
        {
            return;
        }
        
        //方式一 ，控制集合大小 绑定 控制节点的树高，将小的集合对应的根节点合并给大的集合的根节点，使的集合更大
        if ($this->sz[$q_root] < $this->sz[$p_root])
        {
            $this->parent[$p_root] = $q_root;
            $this->sz[$p_root] += $this->sz[$p_root];

        }
        else
        {
            $this->parent[$q_root] = $p_root;
            $this->sz[$q_root] += $this->sz[$q_root];
        }
        
//        //方式二 精准控制树高
//        if ($this->rank[$q_root] < $this->rank[$p_root])
//        {
//            $this->parent[$p_root] = $q_root;
//        }
//        elseif ($this->rank[$q_root] > $this->rank[$p_root])
//        {
//            $this->parent[$q_root] = $p_root;
//        }
//        else
//        {
//            $this->parent[$p_root] = $q_root;
//            $this->rank[$q_root] += 1;
//        }
    }
}
$obj = new QuickFindOptimizationTWo($n);
$before_time = microtime(true);
for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->mergeElement($a,$b);
}

for($i=0;$i<$n;$i++)
{
    $a = mt_rand(0,PHP_INT_MAX) % $n;
    $b = mt_rand(0,PHP_INT_MAX) % $n;
    $obj->isConnect($a,$b);
}
$after_time = microtime(true);
$time = round($after_time-$before_time,3);
echo 'QuickFindOptimizationTWo耗时'.$time.'秒';



